/** Copyright (c) JinLiwei 2022-present  */

/**
 * 大小顶堆的js实现
 * 
 */
class Heap {
    constructor(compareFunc) {
        if (typeof compareFunc !== 'function') {
            throw new Error('compareFunc((a, b) => a -b) of Heap must be given in constructor');
        }
        this._capacity = 0;
        this._datas = [];
        this.compareFunc = compareFunc;
    }

    setCompareFunc = compareFunc => this.compareFunc = compareFunc;

    isIndexOk = index => {
        return index < this._capacity && index >= 0;
    }

    getLeftChild = index => {
        const leftChildIndex = 2 * index + 1;
        if (this.isIndexOk(index) && this.isIndexOk(leftChildIndex)) {
            return [leftChildIndex, this._datas[leftChildIndex]];
        }
        return null;
    }

    getRightChild = index => {
        const rightChildIndex = 2 * index + 2;
        if (this.isIndexOk(index) && this.isIndexOk(rightChildIndex)) {
            return [rightChildIndex, this._datas[rightChildIndex]];
        }
        return null;
    }

    getParent = index => {
        const parentIndex = parseInt((index - 1) / 2);
        if (this.isIndexOk(index) && this.isIndexOk(parentIndex)) {
            return [parentIndex, this._datas[parentIndex]];
        }
        return null;
    }

    swap = (indexOne, indexTwo) => {
        if (this.isIndexOk(indexOne) && this.isIndexOk(indexTwo)) {
            const tmpItem = this._datas[indexOne];
            this._datas[indexOne] = this._datas[indexTwo];
            this._datas[indexTwo] = tmpItem;
        }
    }

    isRoot = index => index === 0;

    offer = item => {
        this._datas.push(item);
        this._capacity += 1;
        this.adjustOffer(this._capacity - 1);
    }

    getItemByIndex = index => {
        if (this.isIndexOk(index)) {
            return this._datas[index];
        }
        return null;
    }

    peek = () => this.getItemByIndex(0);

    adjustOffer = curIndex => {
        if (this.isRoot(curIndex)) {
            return;
        }
        const parent = this.getParent(curIndex);
        if (parent) {
            if (this.compareFunc(this.getItemByIndex(curIndex), parent[1]) < 0) {
                this.swap(curIndex, parent[0]);
                this.adjustOffer(parent[0]);
            }
        }
    }

    pull = () => {
        if (this._capacity < 1) {
            return null;
        }
        if (this._capacity === 1) {
            const retItem = this.getItemByIndex(0);
            this._capacity -= 1;
            this._datas.splice(this._datas.length - 1, 1);
            return retItem;
        }
        const retItem = this.getItemByIndex(0);
        this._datas[0] = this.getItemByIndex(this._datas.length - 1);
        this._capacity -= 1;
        this._datas.splice(this._datas.length - 1, 1);
        this.adjustPull(0);
        return retItem;
    }

    adjustPull = curIndex => {
        const leftChild = this.getLeftChild(curIndex);
        const rightChild = this.getRightChild(curIndex);
        if (!leftChild && !rightChild) {
            return;
        }
        const curItem = this.getItemByIndex(curIndex);
        if (leftChild && rightChild) {
            if (this.compareFunc(curItem, leftChild[1]) <= 0 && this.compareFunc(curItem, rightChild[1]) <= 0) {
                return;
            }
            if (this.compareFunc(leftChild[1], rightChild[1]) < 0) {
                this.swap(curIndex, leftChild[0]);
                this.adjustPull(leftChild[0]);
            } else {
                this.swap(curIndex, rightChild[0]);
                this.adjustPull(rightChild[0]);
            }
        } else if (leftChild) {
            if (this.compareFunc(curItem, leftChild[1]) <= 0) {
                return;
            } else {
                this.swap(curIndex, leftChild[0]);
                this.adjustPull(leftChild[0]);
            }
        }
    }

    size = () => this._capacity;

    restore = () => {
        this._capacity = 0;
        this._datas = [];
    }
}

module.exports = {
    Heap
}